{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Add One Row to Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: addOneRow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #在二叉树中增加一行"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉树的根&nbsp;<code>root</code>&nbsp;和两个整数 <code>val</code> 和&nbsp;<code>depth</code>&nbsp;，在给定的深度&nbsp;<code>depth</code>&nbsp;处添加一个值为 <code>val</code> 的节点行。</p>\n",
    "\n",
    "<p>注意，根节点&nbsp;<code>root</code>&nbsp;位于深度&nbsp;<code>1</code>&nbsp;。</p>\n",
    "\n",
    "<p>加法规则如下:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>给定整数&nbsp;<code>depth</code>，对于深度为&nbsp;<code>depth - 1</code> 的每个非空树节点 <code>cur</code> ，创建两个值为 <code>val</code> 的树节点作为 <code>cur</code> 的左子树根和右子树根。</li>\n",
    "\t<li><code>cur</code> 原来的左子树应该是新的左子树根的左子树。</li>\n",
    "\t<li><code>cur</code> 原来的右子树应该是新的右子树根的右子树。</li>\n",
    "\t<li>如果 <code>depth == 1 </code>意味着&nbsp;<code>depth - 1</code>&nbsp;根本没有深度，那么创建一个树节点，值 <code>val </code>作为整个原始树的新根，而原始树就是新根的左子树。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/03/15/addrow-tree.jpg\" style=\"height: 231px; width: 500px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [4,2,6,3,1,5], val = 1, depth = 2\n",
    "<strong>输出:</strong> [4,1,1,2,null,null,6,3,1,5]</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/03/11/add2-tree.jpg\" style=\"height: 277px; width: 500px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [4,2,null,3,1], val = 1, depth = 3\n",
    "<strong>输出:</strong>  [4,2,null,1,1,3,null,null,1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>节点数在&nbsp;<code>[1, 10<sup>4</sup>]</code>&nbsp;范围内</li>\n",
    "\t<li>树的深度在&nbsp;<code>[1, 10<sup>4</sup>]</code>范围内</li>\n",
    "\t<li><code>-100 &lt;= Node.val &lt;= 100</code></li>\n",
    "\t<li><code>-10<sup>5</sup>&nbsp;&lt;= val &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= depth &lt;= the depth of tree + 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [add-one-row-to-tree](https://leetcode.cn/problems/add-one-row-to-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [add-one-row-to-tree](https://leetcode.cn/problems/add-one-row-to-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,6,3,1,5]\\n1\\n2', '[4,2,null,3,1]\\n1\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def addOneRow(self, root, v, d):\n",
    "    \"\"\"\n",
    "    :type root: TreeNode\n",
    "    :type v: int\n",
    "    :type d: int\n",
    "    :rtype: TreeNode\n",
    "    \"\"\"\n",
    "    if d == 1:\n",
    "      newRoot = TreeNode( v )\n",
    "      newRoot.left = root\n",
    "      return newRoot\n",
    "\n",
    "    depth, curLevel, nextLevel = 1, list(), [ root ]\n",
    "    while depth < d - 1:\n",
    "      curLevel, nextLevel = nextLevel, curLevel\n",
    "      nextLevel.clear()\n",
    "      depth += 1\n",
    "\n",
    "      for node in curLevel:\n",
    "        if node.left != None:\n",
    "          nextLevel.append( node.left )\n",
    "        if node.right != None:\n",
    "          nextLevel.append( node.right )\n",
    "    curLevel = nextLevel\n",
    "\n",
    "    for node in curLevel:\n",
    "      newLeft = TreeNode( v )\n",
    "      newLeft.left = node.left\n",
    "      node.left = newLeft\n",
    "      newRight = TreeNode( v )\n",
    "      newRight.right = node.right\n",
    "      node.right = newRight\n",
    "\n",
    "    return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOneRow(self, root, v, d):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type v: int\n",
    "        :type d: int\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if d == 1:\n",
    "            new_root = TreeNode(v)\n",
    "            new_root.left = root\n",
    "            # new_root.left = None\n",
    "            return new_root\n",
    "        cur = [root]\n",
    "        deep = 1\n",
    "        while deep!= d-1 :\n",
    "            next_level = []\n",
    "            for node in cur:\n",
    "                if node.left:\n",
    "                    next_level.append(node.left)\n",
    "                if node.right:\n",
    "                    next_level.append(node.right)\n",
    "            deep += 1\n",
    "            cur = next_level\n",
    "        for node in cur:\n",
    "            tmp1 = node.left\n",
    "            node.left = TreeNode(v)\n",
    "            node.left.left = tmp1\n",
    "            tmp2 = node.right\n",
    "            node.right = TreeNode(v)\n",
    "            node.right.right = tmp2\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOneRow(self, root, v, d):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type v: int\n",
    "        :type d: int\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        dummy = TreeNode(0)\n",
    "        dummy.left, que = root, collections.deque([dummy])\n",
    "        for i in range(d - 1):\n",
    "            l = len(que)\n",
    "            for i in range(l):\n",
    "                cur = que.popleft()\n",
    "                if cur.left:\n",
    "                    que.append(cur.left)\n",
    "                if cur.right:\n",
    "                    que.append(cur.right)\n",
    "        for i in que:\n",
    "            l, r = TreeNode(v), TreeNode(v)\n",
    "            i.left, l.left, i.right, r.right = l, i.left, r, i.right\n",
    "        return dummy.left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOneRow(self, root, v, d):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type v: int\n",
    "        :type d: int\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        nodes = []\n",
    "        for i in range(d-1):\n",
    "            if not nodes:\n",
    "                nodes.append(root)\n",
    "            else:\n",
    "                temp = []\n",
    "                for node in nodes:\n",
    "                    if node.left:\n",
    "                        temp.append(node.left)\n",
    "                    if node.right:\n",
    "                        temp.append(node.right)\n",
    "                nodes = temp\n",
    "        if not nodes:\n",
    "            node = TreeNode(v)\n",
    "            node.left = root\n",
    "            return node\n",
    "        for node in nodes:\n",
    "            templ = TreeNode(v)\n",
    "            tempr = TreeNode(v)\n",
    "            templ.left = node.left\n",
    "            tempr.right = node.right\n",
    "            node.left = templ\n",
    "            node.right = tempr\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOneRow(self, root, v, d):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type v: int\n",
    "        :type d: int\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return root\n",
    "        if d == 1:\n",
    "            l = TreeNode(v)\n",
    "            l.left = root\n",
    "            root = l\n",
    "        elif d == 2:\n",
    "            l = TreeNode(v)\n",
    "            r = TreeNode(v)\n",
    "            l.left = root.left\n",
    "            r.right = root.right\n",
    "            root.left = l\n",
    "            root.right = r\n",
    "        else:\n",
    "            root.left = self.addOneRow(root.left,v,d-1)\n",
    "            root.right = self.addOneRow(root.right,v,d-1)\n",
    "        return root\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def addOneRow(self, root, v, d):\n",
    "        def dfs(r, dep):\n",
    "            if not r:\n",
    "                return\n",
    "            if dep == d - 1:\n",
    "                t = TreeNode(v)\n",
    "                r.left, t.left = t, r.left\n",
    "                t = TreeNode(v)\n",
    "                r.right, t.right = t, r.right\n",
    "                return\n",
    "            else:\n",
    "                dfs(r.left, dep + 1)\n",
    "                dfs(r.right, dep + 1)\n",
    "                \n",
    "        if d == 1:\n",
    "            t = TreeNode(v)\n",
    "            t.left = root\n",
    "            return t\n",
    "        dfs(root, 1)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOneRow(self, root, v, d):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type v: int\n",
    "        :type d: int\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if d == 1:\n",
    "            r = TreeNode(v)\n",
    "            r.left = root\n",
    "            return r\n",
    "        def dfs(node, d, v, cd):\n",
    "            if not node:\n",
    "                return\n",
    "            if cd == d - 1:\n",
    "                l, r = node.left, node.right\n",
    "                node.left = TreeNode(v)\n",
    "                node.right = TreeNode(v)\n",
    "                node.left.left = l\n",
    "                node.right.right = r\n",
    "            elif cd < d - 1:\n",
    "                dfs(node.left, d, v, cd + 1)\n",
    "                dfs(node.right, d, v, cd + 1)\n",
    "        dfs(root, d, v, 1)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:\n",
    "        if d == 1:\n",
    "            n = TreeNode(v)\n",
    "            n.left = root\n",
    "            return n\n",
    "        node_list = []\n",
    "        if root:\n",
    "            node_list.append(root)\n",
    "        for i in range(1, d-1):\n",
    "            new_list = []\n",
    "            for node in node_list:\n",
    "                if node.left:\n",
    "                    new_list.append(node.left)\n",
    "                if node.right:\n",
    "                    new_list.append(node.right)\n",
    "            node_list = new_list\n",
    "        if node_list:\n",
    "            for node in node_list:\n",
    "                l = TreeNode(v)\n",
    "                l.left = node.left\n",
    "                r = TreeNode(v)\n",
    "                r.right = node.right\n",
    "                node.left = l\n",
    "                node.right = r\n",
    "            return root\n",
    "        else:\n",
    "            return None\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:\n",
    "        if d==1:\n",
    "            head = TreeNode(v)\n",
    "            head.left = root\n",
    "            return head\n",
    "        \n",
    "        queue = [root]\n",
    "\n",
    "        while queue and d>2:\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "\n",
    "            d -= 1\n",
    "\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "\n",
    "            temp = TreeNode(v)\n",
    "            if node.left:\n",
    "                temp.left = node.left\n",
    "            node.left = temp\n",
    "\n",
    "            temp = TreeNode(v)\n",
    "            if node.right:\n",
    "                temp.right = node.right\n",
    "            node.right = temp\n",
    "            \n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:\n",
    "        if d == 1:\n",
    "            t, t.left = TreeNode(v), root\n",
    "            return t\n",
    "\n",
    "        queue = [root]\n",
    "        level, flag =0, True\n",
    "        while queue and flag:\n",
    "            temp = []\n",
    "            level += 1\n",
    "            for node in queue:\n",
    "                if level == d-1:\n",
    "                    t = TreeNode(v)\n",
    "                    t.left, node.left = node.left, t\n",
    "                    t = TreeNode(v)\n",
    "                    t.right, node.right = node.right, t\n",
    "                    flag = False\n",
    "                else:\n",
    "                    if node.left:\n",
    "                        temp.append(node.left)\n",
    "                    if node.right:\n",
    "                        temp.append(node.right)\n",
    "            queue = temp \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:\n",
    "        if d == 1:\n",
    "            newroot = TreeNode(v)\n",
    "            newroot.left = root\n",
    "            return newroot\n",
    "        queue = deque([root])\n",
    "        level = 1\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            if level == d - 1:\n",
    "                for i in range(length):\n",
    "                    curr = queue.popleft()\n",
    "                    nodel = TreeNode(v)\n",
    "                    nodel.left = curr.left\n",
    "                    curr.left = nodel\n",
    "                    noder = TreeNode(v)\n",
    "                    noder.right = curr.right\n",
    "                    curr.right = noder\n",
    "                return root\n",
    "            else:\n",
    "                for i in range(length):\n",
    "                    curr = queue.popleft()\n",
    "                    if curr.left:\n",
    "                        queue.append(curr.left)\n",
    "                    if curr.right:\n",
    "                        queue.append(curr.right)\n",
    "            level += 1\n",
    "        return root\n",
    "\n",
    "\n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:\n",
    "        if d ==1:\n",
    "            new_root = TreeNode(v)\n",
    "            new_root.left = root\n",
    "            return new_root\n",
    "        stack = [root]\n",
    "        while d > 2 :\n",
    "            for i in range(len(stack)):\n",
    "                node = stack.pop(0)\n",
    "                if node.left:\n",
    "                    stack.append(node.left)\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "            d -= 1\n",
    "        for i in range(len(stack)):\n",
    "            node = stack.pop(0)\n",
    "            new_left = TreeNode(v)\n",
    "            temp_left = node.left\n",
    "            node.left = new_left\n",
    "            new_left.left = temp_left\n",
    "            new_right = TreeNode(v)\n",
    "            temp_right = node.right\n",
    "            node.right = new_right\n",
    "            new_right.right = temp_right\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:\n",
    "        if d == 1:\n",
    "            node_n = TreeNode(v)\n",
    "            node_n.left = root\n",
    "            return node_n\n",
    "        stack = [root]\n",
    "        if d == 2:\n",
    "            if root:\n",
    "#                if root.left:\n",
    "                tmp = root.left\n",
    "                newtmp = TreeNode(v)\n",
    "                root.left = newtmp\n",
    "                newtmp.left = tmp\n",
    "#                if root.right:\n",
    "                tmp = root.right\n",
    "                newtmp = TreeNode(v)\n",
    "                root.right = newtmp\n",
    "                newtmp.right = tmp\n",
    "            return root               \n",
    "        while d > 2:\n",
    "            if not stack:\n",
    "                return root\n",
    "            list_v = []\n",
    "            while len(stack) > 0:\n",
    "                tmp = stack.pop()\n",
    "                if tmp.left:\n",
    "                    list_v.append(tmp.left)\n",
    "                if tmp.right:\n",
    "                    list_v.append(tmp.right)\n",
    "            stack = list_v\n",
    "            d -= 1\n",
    "        print(stack)\n",
    "        if d == 2:\n",
    "            for node in stack:\n",
    "#                if node.left:\n",
    "                tmp = node.left\n",
    "                newtmp = TreeNode(v)\n",
    "                node.left = newtmp\n",
    "                newtmp.left = tmp\n",
    "#                if node.right:\n",
    "                tmp = node.right\n",
    "                newtmp = TreeNode(v)\n",
    "                node.right = newtmp\n",
    "                newtmp.right = tmp\n",
    "        return root                    \n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "                \n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:\n",
    "        import queue\n",
    "        if d == 1:\n",
    "            tn = TreeNode(v)\n",
    "            tn.left = root\n",
    "            return tn\n",
    "        q = queue.Queue()\n",
    "        q.put((root, 1))\n",
    "        while q.qsize() > 0:\n",
    "            tn, deep = q.get()\n",
    "            if deep == d - 1:\n",
    "                ltn = TreeNode(v)\n",
    "                ltn.left = tn.left\n",
    "                tn.left = ltn\n",
    "                rtn = TreeNode(v)\n",
    "                rtn.right = tn.right\n",
    "                tn.right = rtn\n",
    "            else:\n",
    "                if tn.left != None:\n",
    "                    q.put((tn.left, deep+1))\n",
    "                if tn.right != None:\n",
    "                    q.put((tn.right, deep+1))\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:\n",
    "        if d == 1:\n",
    "            out = TreeNode(v)\n",
    "            out.left = root\n",
    "            return out\n",
    "        i = 2\n",
    "        queue = [root]\n",
    "        while i < d:\n",
    "            next_queue = []\n",
    "            for node in queue:\n",
    "                if node.left:\n",
    "                    next_queue.append(node.left)\n",
    "                if node.right:\n",
    "                    next_queue.append(node.right)\n",
    "            queue = next_queue\n",
    "            i += 1\n",
    "        for node in queue:\n",
    "            tmp_1 = node.left\n",
    "            tmp_2 = node.right\n",
    "            node.left = TreeNode(v)\n",
    "            node.left.left = tmp_1\n",
    "            node.right = TreeNode(v)\n",
    "            node.right.right = tmp_2\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:\n",
    "        if d == 1:\n",
    "            p = TreeNode(v)\n",
    "            p.left = root\n",
    "            return p\n",
    "        queue = [root]\n",
    "        deep = 2\n",
    "        while deep < d:\n",
    "            length = len(queue)\n",
    "            for _ in range(length):\n",
    "                p = queue.pop(0)\n",
    "                if p.left:\n",
    "                    queue.append(p.left)\n",
    "                if p.right:\n",
    "                    queue.append(p.right)\n",
    "            deep += 1\n",
    "        for node in queue:\n",
    "            Left = TreeNode(v)\n",
    "            Right = TreeNode(v)\n",
    "            Left.left = node.left\n",
    "            Right.right = node.right\n",
    "            node.left = Left\n",
    "            node.right= Right\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:\n",
    "        # 如果d是1，则直接创立一个node，并把root赋予给node.left并返回node\n",
    "        if d == 1:\n",
    "            node = TreeNode(v)\n",
    "            node.left = root\n",
    "            return node\n",
    "        # 当前深度为1\n",
    "        current = 1\n",
    "        queue = [root]\n",
    "        # 否则开始正常的bfs\n",
    "        while len(queue) > 0:\n",
    "            size = len(queue)\n",
    "            for i in range(size):\n",
    "                node = queue.pop(0)\n",
    "                left = node.left\n",
    "                right = node.right\n",
    "                # 因为要在深度的上一层进行修改，所以是d-1\n",
    "                if current == d-1:\n",
    "                    node.left = TreeNode(v)\n",
    "                    node.right = TreeNode(v)\n",
    "                    node.left.left = left\n",
    "                    node.right.right = right\n",
    "                    # 添加完所有该层节点，可以直接return root了，这里用break一样\n",
    "                    if i == size-1:\n",
    "                        break\n",
    "                # 否则开始正常的bfs\n",
    "                if node.left is not None:\n",
    "                    queue.append(node.left)\n",
    "                if node.right is not None:\n",
    "                    queue.append(node.right)\n",
    "            current += 1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def addOneRow(self, root: TreeNode, val: int, depth: int) -> TreeNode:\n",
    "        if depth==1:\n",
    "            cur=TreeNode(val)\n",
    "            cur.left=root\n",
    "            return cur\n",
    "        queue=[root]\n",
    "        for i in range(depth-2):\n",
    "            tmp=[]\n",
    "            for node in queue:\n",
    "                if node.left:\n",
    "                    tmp.append(node.left)\n",
    "                if node.right:\n",
    "                    tmp.append(node.right)\n",
    "            queue=tmp\n",
    "        for node in queue:\n",
    "            left=TreeNode(val)\n",
    "            right=TreeNode(val)\n",
    "            left.left=node.left\n",
    "            right.right=node.right\n",
    "            node.left=left\n",
    "            node.right=right\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:\n",
    "        if depth == 1:\n",
    "            t = TreeNode()\n",
    "            t.val = val\n",
    "            t.left = root\n",
    "            return t \n",
    "        d = 0\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            d += 1\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if d == depth-1:\n",
    "                    left, right = TreeNode(val=val),TreeNode(val=val)\n",
    "                    left.left = node.left\n",
    "                    right.right = node.right\n",
    "                    node.left = left\n",
    "                    node.right = right\n",
    "                else:\n",
    "                    if node.left:\n",
    "                        q.append(node.left)\n",
    "                    if node.right:\n",
    "                        q.append(node.right)\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:\n",
    "        if depth==1:\n",
    "            node = TreeNode(val)\n",
    "            node.left = root\n",
    "            return node\n",
    "        dict_node = {}\n",
    "        curr_dep = 1\n",
    "        layer_node=[root]\n",
    "        while layer_node!=[]:\n",
    "            layer_width = len(layer_node)\n",
    "            #print(layer_width)\n",
    "            tmp = []\n",
    "            if curr_dep==depth-1:\n",
    "                #print('curr_dep',curr_dep)\n",
    "                #print(layer_node)\n",
    "                #print(root)\n",
    "                for node in layer_node:\n",
    "                    insert1 = TreeNode(val)\n",
    "                    insert1.left = node.left\n",
    "                    insert2 = TreeNode(val)\n",
    "                    insert2.right = node.right\n",
    "                    node.left = insert1\n",
    "                    node.right = insert2\n",
    "                    \n",
    "                return root\n",
    "            else:\n",
    "                for i in range(layer_width):\n",
    "                    node = layer_node.pop(0)\n",
    "                    if node.left:\n",
    "                        layer_node.append(node.left)\n",
    "                    if node.right:\n",
    "                        layer_node.append(node.right)\n",
    "            #print(root)\n",
    "            curr_dep = curr_dep+1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:\n",
    "        if depth == 1:\n",
    "            return TreeNode(val,root,None)\n",
    "        q = [[root,1]]\n",
    "        while q:\n",
    "            tmp = []\n",
    "            for node,i in q:\n",
    "                if i == depth:       # i==depth-1循环完了，说明所有i=depth-1的node增加完了\n",
    "                    return root\n",
    "                if i == depth-1:     # 如果在这里return root，就只有第一个node加了，后面都没加。\n",
    "                    node.left = TreeNode(val,node.left,None)\n",
    "                    node.right = TreeNode(val,None,node.right)\n",
    "\n",
    "                if node.left:\n",
    "                    tmp.append([node.left,i+1])\n",
    "                if node.right:\n",
    "                    tmp.append([node.right,i+1])\n",
    "\n",
    "            q= tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:\n",
    "        if depth == 1:\n",
    "            return TreeNode(val, left=root)\n",
    "        q = []\n",
    "        q.append(root)\n",
    "        dep = 1\n",
    "        while q:\n",
    "            l = len(q)\n",
    "            cur = []\n",
    "            for i in range(l):\n",
    "                n = q.pop(0)\n",
    "                cur.append(n)\n",
    "                if n.left:\n",
    "                    q.append(n.left)\n",
    "                if n.right:\n",
    "                    q.append(n.right)\n",
    "            if dep == depth - 1:\n",
    "                for node in cur:\n",
    "                    left = node.left\n",
    "                    right = node.right\n",
    "                    node.left = TreeNode(val, left=left)\n",
    "                    node.right = TreeNode(val, right=right)\n",
    "                return root\n",
    "            dep += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "from typing import Optional\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param root:\n",
    "        :param val:\n",
    "        :param depth:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        if depth == 1:\n",
    "            newNode = TreeNode(val)\n",
    "            newNode.left = root\n",
    "            return newNode\n",
    "        dq = deque()\n",
    "        dq.append((root, 1))\n",
    "        toappend = []\n",
    "        m1 = {}\n",
    "        while len(dq) > 0:\n",
    "            first, dp = dq.popleft()\n",
    "            if dp not in m1:\n",
    "                m1[dp] = [first]\n",
    "            else:\n",
    "                m1[dp].append(first)\n",
    "            if first.left:\n",
    "                dq.append((first.left, dp + 1))\n",
    "            if first.right:\n",
    "                dq.append((first.right, dp + 1))\n",
    "            if dp == depth - 1:\n",
    "                toappend.append(first)\n",
    "            if dp > depth:\n",
    "                break\n",
    "        if len(toappend) > 0:\n",
    "            for i in toappend:\n",
    "                if i.left:\n",
    "                    tmp = i.left\n",
    "                    newnode = TreeNode(val)\n",
    "                    i.left = newnode\n",
    "                    newnode.left = tmp\n",
    "                else:\n",
    "                    v1 = TreeNode(val)\n",
    "                    i.left = v1\n",
    "                if i.right:\n",
    "                    tmp = i.right\n",
    "                    newnode = TreeNode(val)\n",
    "                    i.right = newnode\n",
    "                    newnode.right = tmp\n",
    "                else:\n",
    "                    v1 = TreeNode(val)\n",
    "                    i.right = v1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:\n",
    "        if not root:\n",
    "            return\n",
    "\n",
    "        if d == 1:\n",
    "            node = TreeNode(v)\n",
    "            node.left = root\n",
    "            return node\n",
    "\n",
    "        if d == 2:\n",
    "            L = TreeNode(v)  # 新左节点\n",
    "            R = TreeNode(v)  # 新右节点\n",
    "\n",
    "            L.left = root.left\n",
    "            R.right = root.right\n",
    "\n",
    "            root.left = L\n",
    "            root.right = R\n",
    "            return root\n",
    "\n",
    "        self.addOneRow(root.left, v, d-1)\n",
    "        self.addOneRow(root.right, v, d-1)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:\n",
    "        if depth == 1:\n",
    "            return TreeNode(val, root, None)\n",
    "        level = [root]\n",
    "        for i in range(2, depth):\n",
    "            temp = []\n",
    "            for node in level:\n",
    "                if node.left:\n",
    "                    temp.append(node.left)\n",
    "                if node.right:\n",
    "                    temp.append(node.right)\n",
    "            level = temp\n",
    "        for node in level:\n",
    "            node.left = TreeNode(val, node.left, None)\n",
    "            node.right = TreeNode(val, None, node.right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:\n",
    "        if root:\n",
    "            nodes = [root]\n",
    "        else:\n",
    "            return None\n",
    "        if depth == 1:\n",
    "            root_ = TreeNode(val)\n",
    "            root_.left = root\n",
    "            return root_\n",
    "        else:\n",
    "            current_depth = 1\n",
    "            while current_depth < depth - 1:\n",
    "                lens = len(nodes)\n",
    "                # print(lens)\n",
    "                for i in range(lens):\n",
    "                    item = nodes.pop(0)\n",
    "                    if item.left:\n",
    "                        nodes.append(item.left)\n",
    "                    if item.right:\n",
    "                        nodes.append(item.right)\n",
    "                current_depth += 1\n",
    "            # print(nodes)\n",
    "            for node in nodes:\n",
    "                if node.left:\n",
    "                    tmp = node.left\n",
    "                    node.left = TreeNode(val)\n",
    "                    node.left.left = tmp\n",
    "                else:\n",
    "                    node.left = TreeNode(val)\n",
    "\n",
    "                if node.right:\n",
    "                    tmp = node.right\n",
    "                    node.right = TreeNode(val)\n",
    "                    node.right.right = tmp\n",
    "                else:\n",
    "                    node.right = TreeNode(val)\n",
    "            return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:\n",
    "        if depth == 1:\n",
    "            return TreeNode(val, root)\n",
    "        \n",
    "        queue = [root]\n",
    "        d = 1\n",
    "\n",
    "        while queue:\n",
    "            if d == depth - 1:\n",
    "                for _ in range(len(queue)):\n",
    "                    node = queue.pop(0)\n",
    "                    left_old, right_old = node.left, node.right\n",
    "                    node.left = TreeNode(val, left_old)\n",
    "                    node.right = TreeNode(val, None, right_old)\n",
    "                return root\n",
    "            else:\n",
    "                for _ in range(len(queue)):\n",
    "                    node = queue.pop(0)\n",
    "                    if node.left:\n",
    "                        queue.append(node.left)\n",
    "                    if node.right:\n",
    "                        queue.append(node.right)\n",
    "            d += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:\n",
    "\n",
    "        if depth == 1:\n",
    "            newNode = TreeNode(val)\n",
    "            newNode.left = root\n",
    "            return newNode\n",
    "\n",
    "        def dfs(node, h):\n",
    "\n",
    "            if not node:\n",
    "                return\n",
    "            \n",
    "            if h == depth -1:\n",
    "                \n",
    "                newNode = TreeNode(val)\n",
    "                newNode.left = node.left\n",
    "                node.left = newNode\n",
    "                \n",
    "                newNode = TreeNode(val)\n",
    "                newNode.right = node.right\n",
    "                node.right = newNode\n",
    "                \n",
    "                return node\n",
    "\n",
    "            node.left = dfs(node.left, h+1)\n",
    "            node.right = dfs(node.right, h + 1)\n",
    "            return node\n",
    "        \n",
    "        dfs(root, 1)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:\n",
    "        if depth == 1:\n",
    "            tmp = TreeNode(val,left=root)\n",
    "            return tmp\n",
    "        def bfs(root,lvl):\n",
    "            if lvl == depth - 1:\n",
    "                tmpl = TreeNode(val, left=root.left)\n",
    "                tmpr = TreeNode(val, right=root.right)\n",
    "                root.left = tmpl\n",
    "                root.right = tmpr\n",
    "            if root.left:\n",
    "                bfs(root.left,lvl+1)\n",
    "            if root.right:\n",
    "                bfs(root.right,lvl+1)\n",
    "        bfs(root,1)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:\n",
    "        def AddOneRow(n,root):\n",
    "            root_left = TreeNode(val)\n",
    "            root_right = TreeNode(val)\n",
    "            if depth == 1:\n",
    "                root_left.left = root\n",
    "                root = root_left\n",
    "            elif n == depth-1 and root:\n",
    "                root_left.left = root.left\n",
    "                root.left = root_left\n",
    "            # if n == depth-1 and root.right:\n",
    "                root_right.right = root.right\n",
    "                root.right = root_right\n",
    "            elif root:\n",
    "                left = AddOneRow(n+1,root.left)\n",
    "                right = AddOneRow(n+1,root.right)\n",
    "            return root\n",
    "        return AddOneRow(1,root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def addOneRow(self, root: TreeNode, val: int, depth: int) -> TreeNode:\n",
    "        if root == None:\n",
    "            return\n",
    "        if depth == 1:\n",
    "            return TreeNode(val, root, None)\n",
    "        if depth == 2:\n",
    "            root.left = TreeNode(val, root.left, None)\n",
    "            root.right = TreeNode(val, None, root.right)\n",
    "        else:\n",
    "            root.left = self.addOneRow(root.left, val, depth - 1)\n",
    "            root.right = self.addOneRow(root.right, val, depth - 1)\n",
    "        return root\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:\n",
    "        if root == None:\n",
    "            return\n",
    "        if depth == 1:\n",
    "            return TreeNode(val, root, None)\n",
    "        if depth == 2:\n",
    "            root.left = TreeNode(val, root.left, None)\n",
    "            root.right = TreeNode(val, None, root.right)\n",
    "        else:\n",
    "            root.left = self.addOneRow(root.left, val, depth - 1)\n",
    "            root.right = self.addOneRow(root.right, val, depth - 1)\n",
    "        return root"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
